import java.util.HashMap;

public class Test10 {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = m; i >= 0; i--) dp[i][n] = Integer.MAX_VALUE;
        for (int j = n; j >= 0; j--) dp[m][j] = Integer.MAX_VALUE;
        dp[m - 1][n] = dp[m][n - 1] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
//    错了
//    public int calculateMinimumHP(int[][] dungeon) {
//        int m = dungeon.length;
//        int n = dungeon[0].length;
//        int[][] dp = new int[m + 1][n + 1];
//        int[][] lifebar = new int[m + 1][n + 1];
//        for(int i = 0;i <= m;i++) dp[i][0] = 10000000;
//        for(int j = 0;j <= n;j++) dp[0][j] = 10000000;
//        dp[0][1] = dp[1][0] = 0;
//        for(int i = 1;i <= m;i++) {
//            for(int j = 1;j <= n;j++) {
//                if(dungeon[i - 1][j - 1] < 0) {
//                    int left = lifebar[i][j - 1] + dungeon[i - 1][j - 1] > 0 ? dp[i][j - 1] : dp[i][j - 1] - dungeon[i - 1][j - 1] + 1;
//                    int top = lifebar[i - 1][j] + dungeon[i - 1][j - 1] > 0 ? dp[i - 1][j] : dp[i - 1][j] - dungeon[i - 1][j - 1] + 1;
//                    dp[i][j] = Math.min(left,top);
//                    if(left < top) {
//                        lifebar[i][j] = lifebar[i][j - 1] + dungeon[i - 1][j - 1] > 0 ? lifebar[i][j - 1] + dungeon[i - 1][j - 1] : 1;
//                    }else {
//                        lifebar[i][j] =  lifebar[i - 1][j] + dungeon[i - 1][j - 1] > 0 ? lifebar[i - 1][j] + dungeon[i - 1][j - 1] : 1;
//                    }
//                }else {
//                    dp[i][j] = Math.min(dp[i][j - 1],dp[i - 1][j]);
//                    lifebar[i][j] = dp[i][j - 1] < dp[i - 1][j] ? lifebar[i][j - 1] : lifebar[i - 1][j] + dungeon[i - 1][j - 1];
//                }
//            }
//        }
//        for (int i = 1; i <= m; i++) {
//            for (int j = 1; j <= n; j++) {
//                System.out.print(dp[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();
//        for (int i = 1; i <= m; i++) {
//            for (int j = 1; j <= n; j++) {
//                System.out.print(lifebar[i][j] + " ");
//            }
//            System.out.println();
//        }
//        return dp[m][n];
//    }

    public static void main(String[] args) {
        Test10 test10 = new Test10();
        int[][] arr = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
        test10.calculateMinimumHP(arr);
    }

}
